//最小覆盖子串
/*给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

 

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。*/
class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0};
        int hash2[128] = {0};
        for (auto& c : t) {
            hash2[c]++;
        }
        int count = 0;
        int left = 0, right = 0;
        int ret = s.size() + 1;
        int min_index = -1;
        while (right < s.size()) {
            hash1[s[right]]++;
            if (hash1[s[right]] <= hash2[s[right]])
                count++;
            while (count == t.size()) {
                if (ret > right - left + 1) {
                    ret = right - left + 1;
                    min_index = left;
                }
                if (hash1[s[left]] <= hash2[s[left]])
                    count--;
                hash1[s[left]]--;
                left++;
            }
            right++;
        }
        if (min_index == -1)
            return {""};
        else
            return s.substr(min_index, ret);
    }
};

//